package 力扣_树算法.树编号;

import java.util.Deque;
import java.util.LinkedList;

/**958.二叉树的完全性检验
 * @author zx
 * @create 2022-04-11 17:46
 */
public class Num958 {
    //核心关键点：树的size是否等于最后一个节点的index！
    int size = 0;
    int maxIndex = 0;
    public boolean isCompleteTree1(TreeNode root) {
        helper(root,1);
        return size == maxIndex;
    }
    private void helper(TreeNode root, int index){
        if(root == null){
            return;
        }
        size++;
        maxIndex = Math.max(maxIndex,index);
        helper(root.left,index * 2);
        helper(root.right,index * 2 + 1);
    }

    /**
     层序遍历
     思路：当树中出现null节点时，此后都不应该出现非空节点，否则返回false，当树被遍历完，则返回true
     */
    public boolean isCompleteTree2(TreeNode root) {
        boolean flag = true;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null){
                    if (!flag){
                        return false;
                    }
                    queue.offer(node.left);
                } else {
                    flag = false;
                }
                if (node.right != null){
                    if (!flag){
                        return false;
                    }
                    queue.offer(node.right);
                } else {
                    flag = false;
                }
            }
        }
        return true;
    }




    /**
     * @return bit
     */
    public boolean isCompleteTree(TreeNode root) {
        // 引入一个标记位来区分完全二叉树的两种状态：
        // 状态一：此时完全二叉树的每个节点都有左右子树
        // 切换状态的条件：
        // a.当碰到第一个只有左树没有右树的节点
        // b.碰到第一个叶子节点
        // 状态二：位于状态二的完全二叉树全都是叶子节点。
        boolean flag = false;
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(!flag){
                //此时处于第一状态
                if(node.left != null && node.right != null){
                    queue.offer(node.left);
                    queue.offer(node.right);
                }else if(node.left != null && node.right == null){
                    //只有左树没有右树,切换状态
                    flag = true;
                    queue.offer(node.left);
                }else if(node.left == null && node.right == null){
                    //第一个叶子节点
                    flag = true;
                }else if(node.left == null && node.right != null){
                    //只有右树没有左树,反例
                    return false;
                }
            }else{//此时处于第二状态,所有节点都必须是叶子节点,找到一个反例就不是完全二叉树
                if(node.left != null || node.right != null){
                    return false;
                }
            }
        }
        return true;
    }
}
